#!/usr/bin/python
import logging
import sys
import types
import re

global unique_number
unique_number = 0

def get_unique_number():
    global unique_number
    unique_number += 1
    if (unique_number & 0xffff) ==0:
        print unique_number
    return unique_number

def generate_state_from_rule(from_state, input_rule, to_state, rule_stack):
    #print " %s, from %d, through %s,  to %d"%(' '.join([i.name for i in rule_stack]), from_state.id, input_rule.name, to_state.id)
    for one_line in input_rule.children:  
        last_state = from_state
        for one_rule in one_line: 
            if one_rule is not one_line[-1]:
                current_state = State(get_unique_number())
            if one_rule is one_line[-1]:
                current_state = to_state
            last_state.down.append([one_rule, current_state])
            if (type(one_rule) is not types.StringType) and (one_rule is not input_rule) and (one_rule not in rule_stack):
                rule_stack.append(one_rule)
                generate_state_from_rule(last_state, one_rule, current_state, rule_stack)
                rule_stack.pop()
            elif (type(one_rule) is types.StringType):
                #print " from %d, through %s,  to %d"%(last_state.id, one_rule, current_state.id) 
                pass
            elif (one_rule is input_rule):
                #print " from %d, through %s,  to %d"%(last_state.id, one_rule.name, current_state.id) 
                pass
            elif (one_rule in rule_stack):
                #print "%s -> %s"%( ' '.join([i.name for i in rule_stack]), one_rule.name)
                pass
            last_state = current_state


class Nullobj(object):
    def __getattribute__(self, name):
        return self
    def __call__(self, *args, **kwargs):
        return self

class Bnf:
    def __init__(self, input_id, input_name):
        self.id = input_id
        self.name = input_name
        self.children = [] # ored rules, each element is a sequence of sub rules

class Rule:
    def __init__(self, input_id, input_str):
        self.id = input_id 
        self.name = input_str
        self.children = [] 

class Instance(Rule):
    def __init__(self, input_rule):
        self.id = get_unique_number()
        self.name = input_rule.name
        self.children = input_rule.children
        self.up = []
        self.down = []

class State:
    def __init__(self, input_id):
        self.id = input_id
        self.str = None
        self.down = []  #upstream,     [condition, the state going to]
        #self.up = None  #downstream,   the rule coming from
                
def get_rule_by_str(input_str, input_all_rules):
    for rule in input_all_rules:
        if input_str==rule.name:
            return rule
    else:
        tmp_rule = Rule(len(input_all_rules), input_str)
        input_all_rules.append(tmp_rule)
        return tmp_rule
    
def recursive_resolve_rule(rule_name, rule_body, log, out_bnf):
    #hybrid rule, split rule body to sub rules
    new_bnfs = []
    or_sub_seq = []
    want_match = ''
    current_bnf = Bnf(len(out_bnf), rule_name)
    for j in out_bnf:
        if rule_name==j.name:
            break
    else:
        out_bnf.append(current_bnf)
    embed_loop = 0
    embed_sub_seq = []
    #print('rule '+rule_name+' is '+rule_body)
    within_keyword = False
    for sub_rule_str in rule_body.split(' '):
        if sub_rule_str is '':
            continue
        elif sub_rule_str=='<b>': 
            within_keyword = True
        elif sub_rule_str=='</b>':
            within_keyword = False
        #print 'sub rule str is ', sub_rule_str
        #print 'within keyword is ', within_keyword
        index = 0
        if want_match:
            embed_sub_seq.append(sub_rule_str)
            #log.debug('before embed_sub_seq is '+str(embed_sub_seq))
        match = {'[':']', '{':'}'}
        for token in ['[', ']', '{', '}', '|']:
            if (token==sub_rule_str) and (not within_keyword):
                #print('\t\ta meaningful '+token)
                if( (index==4) and (not within_keyword)) :#'|'
                        if not want_match:
                                current_bnf.children.append(or_sub_seq)
                                or_sub_seq = [] #prepare for following sequence
                        else: #embeded '|', ignore
                                pass
                elif( (token in match.keys()) and (not within_keyword) ): 
                    #log.debug(' if first [, want match ], loop 1')
                    if not want_match:
                        want_match = match[token]
                        embed_loop = 1
                        #embed_sub_seq = [token]
                    else:
                        #log.debug('if already in [, embed loop inc')
                        if want_match==match[token]:
                            embed_loop += 1
                    #log.debug('it is '+want_match+token)
                elif not within_keyword: # got ]
                    #log.debug(embed_loop)
                    #log.debug('it is '+want_match+token)
                    #log.debug('if already [, embed loop dec')
                    if want_match==token:
                        embed_loop -= 1
                    #log.debug(embed_loop)
                    #log.debug('after dec, if embed_loop is 0, clear want match')
                    if embed_loop==0:
                        want_match = ''
                        delimiter = embed_sub_seq.pop()
                        #print('after embed_sub_seq is '+str(embed_sub_seq))
                        tmp_bnf_body = ' '.join(embed_sub_seq)
                        embed_sub_seq = []
                        if delimiter=='}':
                            new_bnf_name = ('list '+tmp_bnf_body).replace(' ', '_')
                            #new_bnf_body =  tmp_bnf_body.replace(' ', '_') + ' ' + new_bnf_name.replace(' ', '_') + ' | '+ ' empty '
                            new_bnf_body =   new_bnf_name.replace(' ', '_') + ' ' +  tmp_bnf_body.replace(' ', '_')  + ' | '+ ' empty '
                        elif delimiter==']':
                            new_bnf_name = ('opt '+tmp_bnf_body).replace(' ', '_')
                            new_bnf_body = tmp_bnf_body.replace(' ', '_') + ' | empty '
                        #print('new bnf ', new_bnf_name, ' is ', new_bnf_body)
                        if (new_bnf_name, new_bnf_body) not in new_bnfs:
                            new_bnfs.append([new_bnf_name, new_bnf_body])
                        or_sub_seq.append(new_bnf_name)
            
                        if (len(tmp_bnf_body.strip().split(' '))>1):
                            new_bnf_name = tmp_bnf_body.replace(' ', '_')
                            #print('new bnf ', new_bnf_name, ' is ', tmp_bnf_body)
                            if (new_bnf_name, tmp_bnf_body) not in new_bnfs:
                                new_bnfs.append([new_bnf_name, tmp_bnf_body])
                        #or_sub_seq.append(new_bnf_name)
                #index = 0
                break
            index += 1
        else:
            if not want_match:
                #log.debug('\t\tanother rule '+sub_rule_str)
                or_sub_seq.append(sub_rule_str)
    else: #end of rule_body
        if or_sub_seq:
            current_bnf.children.append(or_sub_seq)
        else:
            log.critical('Empty rule_body')
    #log.debug('current bnf is '+current_bnf.name+' children is '+str(current_bnf.children))    
    for name, bnf in new_bnfs:
        recursive_resolve_rule(name, bnf, log, out_bnf)

def resolve_rules( input_rules, leaf_rule, out_rules, log=Nullobj):
    """
        start rule must be the first input rule
        build Rules from BNF rules.
        The input BNF rule may be like this:
            TargetRule ::=      SubRule1       SubRule2       [ OptRule ]      { ListRule }      SubRule3
    """ 
    bnfs = []
    for one_rule in input_rules: 
        delimiter_index =  one_rule.find('::=')
        if delimiter_index < 0:
            log.critical('No delimiter in input rules') 
        rule_name = one_rule[:delimiter_index].strip()
        rule_body = one_rule[delimiter_index+3:].strip().replace('<b>', ' <b> ').replace('</b>',' </b> ').replace('{',' { ').replace('}',' } ').replace(']',' ] ').replace('[', ' [ ')
        #log.debug ('rule '+ rule_name+ ' is '+ rule_body) 
        if rule_name in leaf_rule.keys():
            #log.debug('a leaf cell '+one_rule)
            continue 
        recursive_resolve_rule(rule_name, rule_body, log, bnfs)

    for bnf in bnfs:
        #print 'One is ', bnf.id, bnf.name, bnf.children
        target_rule = get_rule_by_str(bnf.name, out_rules)
        for or_sub_seq in bnf.children:
            within_keyword = False
            tmp_list = []
            for sub_rule in or_sub_seq:
                if sub_rule=='<b>':
                    tmp_word = ''
                    within_keyword = True
                elif sub_rule=='</b>':
                    within_keyword = False
                elif within_keyword:
                    for ch in sub_rule:
                        if ch.isalpha():
                            tmp_word += ch
                            #print 'alpha is ', ch
                        else: 
                            #print 'nonalpha is ', ch
                            if tmp_word:
                                tmp_list.append(tmp_word)
                                #print 'tmp_word0 is ', tmp_word
                                tmp_word = ''
                            if ch.isspace():
                                pass
                            else:
                                tmp_list.append(re.escape(ch))
                    else: 
                        if tmp_word:
                            tmp_list.append(tmp_word)  
                            #print 'tmp_word1 is ', tmp_word
                else:
                    tmp_rule = get_rule_by_str(sub_rule, out_rules)
                    tmp_list.append(tmp_rule)
            else:
                target_rule.children.append(tmp_list)
    else:
        for key in leaf_rule:
            current_rule = get_rule_by_str(key, out_rules)
            current_rule.children.append([leaf_rule[key]])
                   

class Parser: 
    def __init__(self, input_rules, input_logger=None):
        self.leaf_rule = {
            'one_line_comment'          :r'//[^\n]*',
            'block_comment'             :r'\*[\d\D]*?\*/',
            'escaped_identifier'        :r'\\[^\s]+\s',
            'simple_identifier'         :r'[a-zA-Z_][a-zA-Z0-9_]*',
            'string'                    :r'"[\d\D]*?"',
            'system_function_identifier':r'\$[a-zA-Z0-9_$]+',
            'system_task_identifier'    :r'\$[a-zA-Z0-9_$]+',
            'white_space'               :r'\s+',
            'empty'                     :r'',
            'non_zero_decimal_digit'    :r'[123456789]+',
            'decimal_digit'             :r'[0123456789]+',
            'binary_digit'              :r'[?01xzXZ]',
            'octal_digit'               :r'[01234567?xzXZ]',
            'hex_digit'                 :r'[?xzXZ0123456789abcdefABCDEF]',
            'x_digit'                   :r'[xX]',
            'z_digit'                   :r'[zZ?]',
            'non_zero_unsigned_number'  :r'[12346789]+[_012345678]*',
            'unsigned_number'           :r'[0123456789]+[_0123456789]*',
            'binary_value'              :r'[?01xzZX]+[_?01xzXZ]*',
            'octal_value'               :r'[01234567?xzXZ]+[01234567?xzXZ]*',
            'hex_value'                 :r'[?zxZX0123456789abcdefABCDEF]+[?zxZX0123456789abcdefABCDEF]*'
        } 
        self.rules = []
        self.state = []
        if not input_logger:
            input_logger = Nullobj()
        self.log = input_logger
        resolve_rules(input_rules, self.leaf_rule, self.rules, self.log)
        
        start_rule = self.rules[0]
        from_state = State(get_unique_number()) 
        to_state = State(get_unique_number())

        rule_stack = []
        generate_state_from_rule(from_state, start_rule, to_state, rule_stack) 
        os._exit(3)
                
    def parse(self, text):

        #for i in self.rules:
        #    print 'rule ', i.name
        #    pass
        #    for list in i.children:
        #        print '\t a line '
        #        pass
        #        for rule in list:
        #            if type(rule) is types.StringType:
        #                print '\t\t sub str is', rule
        #                pass
        #            else:
        #                pass
        #                print '\t\t sub rule is ', rule.name
        #                if ( (rule.name not in self.leaf_rule.keys()) and (rule.name not in [i.name for i in self.rules])):
        #                    print 'ERROR an invalid sub rule ', rule.name 

        text_index = 0 
        last_text_index = 0
        line_index = 0 
        column_index = 0
        current_rule = self.rules[0]
        trace_stack = []
        match_stack = []
        trace_stack.append([current_rule, text_index, line_index, column_index])

        def get_sub_rule(input_rule, text_index, line_index, column_index):
            tmp_rule = input_rule.children[line_index][column_index]
            line_index = 0
            column_index = 0
            trace_stack.append([tmp_rule, text_index, line_index, column_index])
            #print '\t'*len(trace_stack), 'pushing', tmp_rule.name, text_index, line_index, column_index
            return [tmp_rule, text_index, line_index, column_index]
        def eat_white_space(text, text_index, trace_stack):
            while re.match(r'\s', text[text_index]):
                text_index += 1
            trace_stack[-1][1] = text_index
            return text_index
        def move_to_next_child(text_index, line_index, column_index, current_rule, trace_stack, match_stack):
            #print '\t'*len(trace_stack), 'move to next child ', line_index, column_index
            if len(trace_stack)==0:
                return current_rule, text_index, line_index, column_index
            #print '\t'*len(trace_stack), 'length is ', len(current_rule.children[line_index])
            if ( column_index < (len(current_rule.children[line_index])-1) ):
                if current_rule is current_rule.children[line_index][column_index+1]:
                    pass
                else:
                    column_index += 1
                    print '\t'*len(trace_stack), 'child inc', current_rule.name,  text_index, line_index, column_index
                    trace_stack.append([current_rule, text_index, line_index, column_index])
                return current_rule, text_index, line_index, column_index
            else:
                trace_stack.pop()
                current_rule, tmp_index, line_index, column_index = trace_stack[-1]
                print '\t'*len(trace_stack), 'child pop', current_rule.name,  text_index, line_index, column_index
                return move_to_next_child(text_index, line_index, column_index, current_rule, trace_stack, match_stack)
        def move_to_next_line(text_index, line_index, column_index,  current_rule, trace_stack):
            #print '\t'*len(trace_stack), 'move to next line', line_index, column_index, current_rule
            if ( line_index < (len(current_rule.children)-1) ):
                line_index += 1
                trace_stack[-1][2] += 1
                column_index = 0
                trace_stack[-1][3] = 0
                print '\t'*len(trace_stack), 'line inc', current_rule.name,  text_index, line_index, column_index
                return [current_rule, text_index, line_index, column_index]
            else:
                trace_stack.pop()
                current_rule, text_index, line_index, column_index = trace_stack[-1]
                print '\t'*len(trace_stack), 'line pop', current_rule.name,  text_index, line_index, column_index
                return move_to_next_line(text_index, line_index, column_index, current_rule, trace_stack )
            
        while(True):
            text_index = eat_white_space(text, text_index, trace_stack)
            if text_index==len(text):
                break
            sub_rule = current_rule.children[line_index][column_index]
            if type(sub_rule) is types.InstanceType:
                current_rule, text_index, line_index, column_index  = get_sub_rule(current_rule, text_index, line_index, column_index)
                print '\t'*len(trace_stack), current_rule.name, text_index, line_index, column_index
                continue
            else:
                if sub_rule=='':
                    if trace_stack==[]:
                        break
                    current_rule, text_index, line_index, column_index = move_to_next_child(text_index, line_index, column_index, current_rule, trace_stack, match_stack)
                else:
                    obj = re.match(sub_rule, text[text_index:])
                    if obj:
                        if trace_stack==[]:
                            break
                        print '\t'*len(trace_stack), 'matched', sub_rule, ' at ', text_index
                        text_index += obj.end()
                        trace_stack[-1][1] = text_index
                        current_rule, text_index, line_index, column_index  = move_to_next_child(text_index, line_index, column_index, current_rule, trace_stack, match_stack)
                    else:
                        current_rule, text_index, line_index, column_index = move_to_next_line(text_index, line_index, column_index, current_rule, trace_stack)
                        #print '\t'*len(trace_stack), 'current rule ', current_rule.name

        for i,j in match_stack:
            if type(i) is types.InstanceType:
                print i.name
            else:
                print i
        return match_stack 
            

if __name__=='__main__':
    text = """ 
        module a (p0, p1, p2, p3);

            output [3:0] p1; 
            input [5:4] p0;
            inout p2; 
            inout p3; 

            initial begin
                $display("hello");
            end

            always@( p0 or p1) begin
                p1 <= p0;
                p0 <= 'h4;
                p2 <= 1;
                p3 <= 2;
            end
        endmodule
    """
    sys.setrecursionlimit(15000)

    mylog = logging.getLogger()
    mylog.setLevel(logging.DEBUG) 
    handler = logging.FileHandler( 'bajie.log', 'w')
    mylog.addHandler(handler) 
    handler = logging.StreamHandler(sys.stdout)
    handler.setLevel(logging.INFO)
    mylog.addHandler(handler) 

    myparser = Parser(open("bnf.txt").readlines(), input_logger=mylog)
    myparser.parse(text)
